import java.util.Stack;

/**
 * Created with IntelliJ IDEA
 * Description: 插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序
 * User: SEKI TOMOKI
 * Date: 2024-09-22
 * Time: 12:09
 */
public class Sort {
    /**
     * 直接插入排序
     * 分析:
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * 插入排序适用于 待排序序列已经基本上趋于有序了
     * @param array
     */
    public static void insertSort(int[] array) {
        //假设这组数据的第一个元素是有序的
        //从第二个元素开始，也就是 i 从 1 下标开始遍历
        for(int i = 1; i < array.length; i++) {
            // tmp 用于存储插入的元素
            int tmp = array[i];
            // tmp 依次和前面的元素进行比较
            int j = i-1;
            for(; j >= 0; j--) {
                if(array[j] > tmp) {
                    //把 j 下标中的元素挪到后面一位
                    array[j+1] = array[j];
                }else {
                    //如果 tmp 已经不小于 j 下标的元素，
                    // 说明从第一个元素到下标 j 都是有序的，j 无需再向前遍历
                    // 跳出循环后把 tmp 中的元素插入到下标 j 后面的位置
                    break;
                }
            }
            //此时已经比较完成，直接插入到 j 下标的后面一个位置
            array[j+1] = tmp;
        }
    }


    /**
     * 希尔排序：插入排序的优化
     * 分析：
     * 先对距离较远的元素进行比较和排序，再逐渐缩小比较的间隔，最终使整个数组有序
     * 时间复杂度：不固定，因为与划分元素组的间隔的选择紧密相关，不同的增量序列会导致不同的时间复杂度
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * 划分的组数从多到少，每组的数据越来越多但越来越有序，提升效率
     * @param array
     */
    public static void shellSort(int[] array) {
        //设元素间隔为 gap，每隔 gap 个元素进行比较。随着 gap 的减小，数组逐渐接近有序
        int gap = array.length;

        while(gap > 1) {
            //gap 每次减半，例如数组长度为 10，初始 gap 为 5，表示间隔为 5 的元素比较，
            //然后 gap 为 2，最后 gap 为 1 时相当于一次标准插入排序。
            gap /= 2;
            shell(array, gap);
        }
    }

    /**
     *对每组进行直接插入排序
     * @param array
     * @param gap
     */
    private static void shell(int[] array, int gap) {
        //i 逐一遍历数组，通过 i 来控制从每个位置开始，针对每个间隔为 gap 的元素组进行插入排序
        for(int i = 1; i < array.length; i++) {
            //步骤和直接插入排序没有区别
            //把 1 改成 gap,是因为每个小组中的每个元素下标相差 gap
            //当把整个数组当做一组的话，每个元素下标位置才是相差 1
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j-=gap) {
                if (array[j] > tmp) {
                    //for 循环中的 j -= gap 是因为在当前组内，元素间隔为 gap，gap 控制跨步的比较和移动
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }

            array[j + gap] = tmp;
        }
    }

    /**
     * 选择排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void selectSort(int[] array) {
        //遍历整个数组
        for(int i = 0; i < array.length; i++) {
            int minIndex = i;
            //在当前 i 下标的后面找出最小值
            for(int j = i+1; j < array.length; j++) {
                //如果 j 下标的值比最小值小，把最小值的下标改成 j
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }

            //最小值与 i 下标的值进行交换
            swap(array, i, minIndex);
        }
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }


    /**
     * 创建大根堆
     * @param array
     */
    private static void createHeap(int[] array) {
        //从最后一棵子树开始调整，找到最后一棵子树的父亲节点
        for(int parent = (array.length-1-1)/2; parent >= 0; parent--) {
            //向下调整
            shiftDown(array, parent, array.length);
        }

    }

    /**
     * 向下调整方法
     * @param array
     * @param parent
     * @param length
     */
    private static void shiftDown(int[] array, int parent, int length) {
        int child = parent*2+1;
        //一直向下调整直到 该 parent节点没有孩子节点
        while(child < length) {
            //让比较大的孩子节点与父亲节点进行比较
            if(child+1 < length && array[child] < array[child+1]) {
                child++;
            }
            if(array[parent] < array[child]) {
                swap(array, parent, child);
                //让孩子节点成为父亲节点继续向下调整
                parent = child;
                child = parent*2+1;
            }else {
                break;//说明该子树已经形成堆，无需再向下调整
            }
        }
    }


    /**
     * 堆排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void heapSort(int[] array) {
        //堆排序先创建大根堆
        createHeap(array);
        //对大根堆进行排序
        int endIndex = array.length-1;//指向未排序数组的最后一位
        while(endIndex > 0) {
            //交换 0 下标和 end 下标的值，把最大值放在最后一个位置
            swap(array, 0, endIndex);
            //对 0 下标元素进行向下调整
            shiftDown(array, 0, endIndex);
            //此时数组的最后一位就是最大值，即已排序，endIndex指向前面一个元素继续排序
            endIndex--;
        }
    }

    /**
     * 冒泡排序
     * 时间复杂度：O(N^2)
     *      优化之后，最好情况下时间复杂度为 O(N)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param array
     */
    public static void bubbleSort(int[] array) {
        //一个有 n 个元素的数组需要比较 n-1 趟，i 比较的是趟数
        for(int i = 0; i < array.length-1; i++) {
            boolean flg = false;//默认该趟不是有序的
            // j 来比较每个数据的大小
            for(int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array, j, j+1);
                    flg = true;
                }
            }
            //如果这一趟比较完，没有交换的步骤说明该数组已经有序，结束循环
            if(!flg) {
                break;
            }
        }
    }

    /**
     * 快速排序
     *时间复杂度：
     *  最好情况：O(N*logN)
     *  最坏情况：O(N^2)  逆序或者有序
     *空间复杂度：
     *  最好情况：O(logN)
     *  最坏情况：O(N)  逆序或者有序
     * @param array
     */
    public static void quickSort(int[] array) {//保证接口的统一性，不在 quickSort 方法本身递归，另写一个方法递归
        quick(array, 0, array.length-1);
    }

    private static void quick(int[] array, int start, int end) {
        //如果 start >= end ，说明该 array 区间只有一个元素或者没有元素
        if(start >= end) {
            return;
        }

        //越往下递归，数据越来越少，整体趋于有序，所以对小区间用直接插入排序更快，
        //有效降低递归树的高度
        if((end - start + 1) <= 15) {//如果这个区间的长度比较小就不继续递归，直接使用插入排序
            insertSort(array, start, end);
            return ;
        }

        //通过三数取中法有效降低递归树的高度
        int index = middleNum(array, start, end);
        //为了将中间值作为基准值，index 和 start 的值交换
        swap(array, index, start);


        //通过划分方法找到 pivot, 使得在 pivot 左边都比 array[pivot]的值小，在 pivot 右边都比 array[pivot]的值大
        int pivot = partitionHole(array, start, end);
        //递归 pivot 的左边和右边的数组区间
        quick(array, start, pivot-1);
        quick(array, pivot+1, end);
    }

    /**
     * 三数取中法: 从 array[left] ,array[mid], array[right] 取中间值
     * 有效降低递归树的高度
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int middleNum(int[] array, int left, int right) {
        int mid = (right + left)/2;
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] > array[left]) {
                return left;
            }else if(array[mid] < array[right]) {
                return right;
            }else {
                return mid;
            }
        }
    }

    /**
     * 插入排序的重载方法，用于快速排序的优化，降低递归树的高度
     * @param array
     * @param left
     * @param right
     */
    private static void insertSort(int[] array, int left, int right) {
        for(int i = left; i <= right; i++) {
            // tmp 用于存储插入的元素
            int tmp = array[i];
            // tmp 依次和前面的元素进行比较
            int j = i-1;
            for(; j >= left; j--) {
                if(array[j] > tmp) {
                    //把 j 下标中的元素挪到后面一位
                    array[j+1] = array[j];
                }else {
                    //如果 tmp 已经不小于 j 下标的元素，
                    // 说明从第一个元素到下标 j 都是有序的，j 无需再向前遍历
                    // 跳出循环后把 tmp 中的元素插入到下标 j 后面的位置
                    break;
                }
            }
            //此时已经比较完成，直接插入到 j 下标的后面一个位置
            array[j+1] = tmp;
        }
    }

    /**
     * 三种划分方法：
     *  1. Hoare法
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partitionHoare(int[] array, int left, int right) {
        //把最左边的元素当做基准值，记录基准值到 tmp
        int tmp = array[left];
        //记录此时基准值的位置
        int i = left;

        while(left < right) {
            // right 找出比基准值小的值就停止遍历准备交换元素，否则向前移动
            while(left < right && array[right] >= tmp) {
                right--;
            }
            // left 找出比基准值大的值就停止遍历准备交换元素，否则向后移动
            while(left < right && array[left] <= tmp) {
                left++;
            }

            //此时 left 指向比基准值大的元素， right 指向比基准值小的元素，交换这两个元素
            swap(array, left, right);
        }

        //此时 left 和 right 相遇，他们两此时指向的元素与基准值的位置交换
        swap(array, i, left);
        //此时 left 和 right 指向的位置就是 pivot,
        //因为此时在 pivot 左边都比 array[pivot]小，
        // 在 pivot 右边都比 array[pivot]大
        return left;
    }

    /**
     * 2.挖坑法(Hoare法的改进)
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partitionHole(int[] array, int left, int right) {
        //把最左边的元素当做基准值，记录基准值到 tmp
        int tmp = array[left];
        //把 left 指向的位置看做挖了一个坑，如果已经划分完成，就让基准值填坑
        while(left < right) {
            // right 找出比基准值小的值就停止遍历，否则向前移动
            while(left < right && array[right] >= tmp) {
                right--;
            }
            //此时用 right 的值补上 left 的坑，right 的坑由 left 补上
            array[left] = array[right];

            // left 找出比基准值大的值就停止遍历，否则向后移动
            while(left < right && array[left] <= tmp) {
                left++;
            }
            //此时用 left 的值补上 right 的坑，left 的坑由 right 补上
            array[right] = array[left];
        }


        //此时 left 和 right 相遇，把基准值插入到他们两此时指向的元素
        array[left] = tmp;
        return left;
    }

    /**
     * 3.前后指针法
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partitionFBPointer(int[] array, int left, int right) {
        int prev = left;// prev: 目前比基准值小的最后一个元素
        int cur = left + 1;
        while(cur <= right) {

            if(array[cur] < array[left] && array[++prev] != cur) {
                //说明此时 prev 的前面一个值就是比基准值小的最后一个元素，
                // prev 此时指向的是比基准值大的第一个值，与 cur 交换
                //让 prev 一直指向比基准值小的最后一个元素
                swap(array, prev, cur);
            }
            cur++;
        }

        //此时 prev 指向的是比基准值小的最后一个元素，且 prev 后边都是比基准值大的值
        swap(array, left, prev);
        return prev;
    }

    /**
     * 快速排序非递归实现
     * @param array
     */
    public static void quickSortNonR(int[] array) {
        int left = 0;
        int right = array.length - 1;
        //创建一个栈用于存储每个区间的左下标和右下标
        Stack<Integer> stack = new Stack<>();
        //通过划分方法找到 pivot, 使得在 pivot 左边都比 array[pivot]的值小，在 pivot 右边都比 array[pivot]的值大
        int pivot = partitionHoare(array, left, right);

        //左边如果有两个元素，把左下标和右下标入栈
        //如果只有一个元素就无需排序
        if(pivot - 1 > left) {
            stack.push(left);
            stack.push(pivot - 1);
        }

        //右边如果有两个元素，把左下标和右下标入栈
        if(pivot + 1 < right) {
            stack.push(pivot + 1);
            stack.push(right);
        }

        while(!stack.empty()) {
            //从栈中取出左下标和右下标作为本次寻找该基准值下标的范围
            right = stack.pop();
            left = stack.pop();

            //通过划分方法找到 pivot, 使得在 pivot 左边都比 array[pivot]的值小，在 pivot 右边都比 array[pivot]的值大
            pivot = partitionHoare(array, left, right);

            //左边如果有两个元素，把左下标和右下标入栈
            //如果只有一个元素就无需排序
            if(pivot - 1 > left) {
                stack.push(left);
                stack.push(pivot - 1);
            }

            //右边如果有两个元素，把左下标和右下标入栈
            if(pivot + 1 < right) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }
}
